package com.it.union;

/**
 * @author : code1997
 * @date : 2021/4/6 21:57
 */
public class QuickUnion extends UnionFind {

    public QuickUnion(int capacity) {
        super(capacity);
    }

    /**
     * 时间复杂度：O(logn)，实际上为树的高度。
     */
    @Override
    public int find(int v) {
        rangeCheck(v);
        while (v != parents[v]) {
            v = parents[v];
        }
        return v;
    }

    /**
     * 时间复杂度：O(2logn)，也即O(logn)。
     */
    @Override
    public void union(int v1, int v2) {
        int p1 = find(v1);
        int p2 = find(v2);
        if (p1 == p2) {
            return;
        }
        parents[p1] = p2;
    }

}
